/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class firstmissingpositive {
    public static int firstMissingPositive(int[] A) {
        for(int i=0;i<A.length;i++){
            if(A[i]>0&&A[i]<=A.length&&A[A[i]-1]>0){//mark pos k value to neg; indicate k+1 exist in array
                A[A[i]-1]=-A[A[i]-1];
            }
        }
        
        for(int i=1;i<=A.length;i++){
            if(A[i-1]>=0){//missing
                return i;
            }
        }
        return A.length+1;
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] A={2};
		System.out.println(firstMissingPositive(A));
	}

}
